% 现有一小偷入室盗窃，可以偷窃的物品数量共有12件
% 物品对应的价值（万）为[5;10;13;4;3;11;13;10;8;16;7;4]； 重量（千克）为[2;5;18;3;2;5;10;4;11;7;14;6]。
% 若小偷能拿的物品总质量最大为46kg，如何选取物品使得总价值最大？

% 目标函数

% value是每个物品的价值，weight是每个物品的数量，ratio是
function f = target_BAG(x,value,weight,ratio,restriction)
    % 物品的总价值（收益）
    Money = sum(x*value);
    % 物品的总重量（损失）
    Lost = sum(x*weight);
    % 如果损失
    if Lost < restriction
        f = Money;
    else
        x=~x;
        Money = sum(x*value);
        f = Money-round((Lost-restriction)*ratio);
    end


% 计算函数

function [GBest_x,GBest_y,Record]= PSO_BAG()
    value = [5;10;13;4;3;11;13;10;8;16;7;4];    % 物品重量
    weight = [2;5;18;3;2;5;10;4;11;7;14;6];     % 物品价值
    restriction = 46;                           % 背包重量限制
    practicle = 20;                             % 粒子数
    max_iteration = 100;
    dimension = size(value,1);                  
    ratio = 2.5; 
    c1 = 2;                                   
    c2 = 2;                                   
    wmin = 0.6;
    wmax = 0.8;
    vmax = 0.8;                               
    time=1;
    %Initialize
    x = round(rand(practicle,dimension));             % 背包问题中的粒子取值为0或1，代表选择物品或不选择物品
    v=rand(practicle,dimension)*(2*vmax)-vmax;
    
    PBest_x = x;
    PBest_y = zeros(1,dimension);
    for i=1:practicle
        PBest_y(i) = target_BAG(PBest_x(i,:),value,weight,ratio,restriction);    %将总价值作为局部最优解
    end
    
    GBest_x = ones(1,dimension);
    GBest_y = 0;
    Record = zeros(1,max_iteration);
    for j=1:practicle
        if PBest_y(j)>GBest_y
            GBest_y = PBest_y(j);
            GBest_x = x(j,:);
        end
    end
    
    while time<=max_iteration
    
        % Personal-Best searching
        for i=1:practicle
            f = target_BAG(x(i,:),value,weight,ratio,restriction);
            if f>PBest_y(i)
                PBest_y(i)=f;
                PBest_x(i,:)=x(i,:);
            end
            
            % Global Best searching
            if PBest_y(i) > GBest_y
                GBest_y = PBest_y(i);
                GBest_x = PBest_x(i,:);
            end
            
            % Updating the speed and position
            w=wmin+rand()*(wmax-wmin);      % weight is dynamic
            v(i,:) = w*v(i,:) + c1*rand()*(PBest_x(i,:)-x(i,:)) + c2*rand()*(GBest_x-x(i,:));
            for ii=1:dimension
                if (v(i,ii)<-vmax)||(v(i,ii)>vmax)
                    v(i,ii)=rand*(2*vmax)-vmax;
                end
            end
            
            vv(i,:)=1./(1+exp(-v(i,:)));
            for k=1:dimension
                if vv(i,k)>rand
                    x(i,k)=1;
                else
                    x(i,k)=0;
                end
            end
            
        end
        
        Record(k) = GBest_y;
        time = time+1;
    end
    
    M = GBest_y;           % the value of the bag
    N = GBest_x*weight;    % the weight of the bag
    disp('---------------------------------------')
    disp(['The final steal value is:',num2str(M)]);
    disp(['The final steal weight is:',num2str(N)]);
    string=strcat('Steal items:',num2str(GBest_x));
    disp(string)